Simplicial vertices in graphs with no induced four-edge path or four-edge antipath, and the $H_6$-conjecture

摘要

Let $\mathcal{G}$ be the class of all graphs with no induced four-edge pathor four-edge antipath. Hayward and Nastos \cite{MS} conjectured that everyprime graph in $\mathcal{G}$ not isomorphic to the cycle of length five iseither a split graph or contains a certain useful arrangement of simplicial andantisimplicial vertices. In this paper we give a counterexample to theirconjecture, and prove a slightly weaker version. Additionally, applying aresult of the first author and Seymour \cite{grow} we give a short proof ofFouquet's result \cite{C5} on the structure of the subclass of bull-free graphscontained in $\mathcal{G}$.